//https://leetcode.cn/problems/kth-largest-element-in-an-array/?envType=problem-list-v2&envId=ex0k24j
//基本就是在二分查找：《算法导论》9.2：期望为线性的选择算法

class Solution {
public:
    int findKthLargest(vector<int>& input, int k) {

        if (input.size() < k || k < 1) {
            return -1;
        }
        int start = 0;
        int end = input.size()-1;
        std::vector<int> index_vec = partition(input,start,end);
        if((index_vec[0] <input.size()-k) && (index_vec[1] > input.size()-k )) {
            return input[index_vec[0]];
        }
        while(index_vec[0]!=input.size()-k){
            if(index_vec[0] > input.size()-k){
                end = index_vec[0] -1;
                index_vec = partition(input,start,end);
            }
            else if (index_vec[0] < input.size()-k) {
                start = index_vec[0] +1;
                index_vec = partition(input,start,end);
            }
        }
        return input[input.size()-k];
    }


    std::vector<int> partition(vector<int>& numbers, int l, int r) {
        int rand_num = (rand()%(r-l+1) + l);
        std::swap(numbers[rand_num],numbers[r]);

        int less = l - 1;
        int more = r;
        while (l < more) {
            if (numbers[l] < numbers[r]) {
                std::swap(numbers[++less], numbers[l++]);
            } else if (numbers[l] > numbers[r]) {
                std::swap(numbers[l], numbers[--more]);
            } else {
                ++l;
            }
        }
        std::swap(numbers[more], numbers[r]);
        return std::vector<int> {++less, more};
    };
};

//小根堆实现
int findKthLargest(std::vector<int>& nums, int k) {
    // 创建一个最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    // 遍历数组
    for (int num : nums) {
        // 如果堆的大小小于 k，将元素添加到堆中
        if (min_heap.size() < k) {
            min_heap.push(num);
        } else if (num > min_heap.top()) {
            // 如果当前元素大于堆顶元素，替换堆顶元素
            min_heap.pop();
            min_heap.push(num);
        }
    }

    // 堆顶元素即为第 k 个大的元素
    return min_heap.top();
}